package class31_morrisTraverse;

public class Morris {
    static class Node{
        public int val;
        public Node left;

        public Node right;

        public Node(int val) {
            this.val = val;
            this.right=null;
            this.left=null;
        }

        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //算法本质：将遍历完左树后应该回到的状态，用指针标了出来
    //用指针标记了这是第几次到，左树如果是第一次到，就先去遍历子树根节点的左树，遍历完了再过来
    //如果是第二次到，那就不去左树了，去子树的右树遍历
    public static void morris(Node head){
        Node cur = head;
        Node mostRight = null;
        while(cur!=null){
            if(cur.left==null){
                cur=cur.right;
            }
            else{
                mostRight=cur.left;
                while(mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    mostRight.right=cur;
                    cur = cur.left;
                } else {
                    mostRight.right=null;
                    cur=cur.right;
                }
            }
        }
    }

    public static void morris_preorder(Node head){
        Node cur = head;
        Node mostRight = null;
        while(cur!=null){
            if(cur.left==null){
                System.out.print(cur.val + " ");//只来一次，在第一次打印
                cur = cur.right;
            }
            else{
                mostRight=cur.left;
                while(mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    System.out.print(cur.val + " ");//要来两次，在第一次打印
                    mostRight.right=cur;
                    cur = cur.left;
                } else {
                    mostRight.right=null;
                    cur = cur.right;
                }
            }
        }
        System.out.println(" ");
    }

    public static void morris_inorder(Node head){
        Node cur = head;
        Node mostRight = null;

        while(cur!=null){
            if(cur.left==null){
                System.out.print(cur.val + " ");
                cur = cur.right;//在去右树之前打印（没有左树，只来一次，直接打印）
            }else{
                mostRight = cur.left;
                while(mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    mostRight.right=cur;
                    cur = cur.left;//进入左树
                }
                else{
                    mostRight.right=null;
                    System.out.print(cur.val + " ");
                    cur=cur.right;//在去右树之前打印（来了第二次，在第二次打印）
                }
            }
        }
        System.out.println(" ");

    }

    public static void morris_postorder(Node head){
        Node cur = head;
        Node mostRight = null;
        while(cur!=null){
            if(cur.left==null){
                cur=cur.right;
            }
            else{
                mostRight=cur.left;
                while(mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    mostRight.right=cur;
                    cur = cur.left;
                } else {
                    mostRight.right=null;
                    printReverseEdge(cur.left);
                    cur=cur.right;
                }
            }
        }
        printReverseEdge(head);
    }

    public static void printReverseEdge(Node head){
        head = reverseEdge(head);
        Node p = head;
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.right;
        }
        head = reverseEdge(head);
    }

    public static Node reverseEdge(Node head){
        Node pre = null;
        Node cur = head;
        Node post = cur.right;
        while(cur!=null){
            cur.right = pre;
            pre = cur;
            cur = post;
            if(post!=null) post = post.right;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);

        morris_preorder(head);
        morris_inorder(head);
        morris_postorder(head);
    }
}
